package algorithm_training.digital_games;

import java.util.*;

/**
 * 给定一个1～N的排列a[i]，每次将相邻两个数相加，得到新序列，再对新序列重复这样的操作，
 * 显然每次得到的序列都比上一次的序列长度少1，最终只剩一个数字。
 * 现在如果知道N和最后得到的数字sum，请求出最初序列a[i]，为1～N的一个排列。若有多种答案，则输出字典序最小的那一个。数据保证有解。
 */
public class Main {
//    static List<List<Integer>> list = new ArrayList<>(); // 用于接收所有全排列的结果集
    static int n;
    static int sum;
    static boolean flag;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        sum = sc.nextInt();
        // 全排列
        int[] num = new int[n];
        for (int i = 0; i < n; i++) {
            num[i] = i + 1;
        }
        boolean[] used = new boolean[n]; // 标记在某个排列结果中当前数是否已经使用过
        int depth = 0; // 递归到第几层
        List<Integer> path = new ArrayList<>(); // 保存选择数字的路径
        wholeArrangement(num, path, depth, used);
//        for (int i = 0; i < list.size(); i++) {
//            List<Integer> tmp = list.get(i);
//            if (count(tmp, n) == sum) {
//                for (int j = 0; j < n; j++) {
//                    System.out.print(tmp.get(j));
//                    if (j != n - 1) {
//                        System.out.print(" ");
//                    }
//                }
//                return;
//            }
//        }
        if (!flag) {
            System.out.print(" ");
        }
    }

    /**
     * 计算数字游戏最终和
     * @param tmp
     * @return
     */
    private static int count(List<Integer> tmp, int size) {
//        int size = tmp.size();
//        if (size == 1) {
//            return tmp.get(0);
//        }
//        List<Integer> cur = new ArrayList<>();
//        for (int i = 0; i < size - 1; i++) {
//            cur.add(tmp.get(i) + tmp.get(i + 1));
//        }
//        int ret = count(cur);
        List<Integer> c = new ArrayList<>(tmp);
        while (size > 1) {
            for (int i = 0; i < size - 1; i++) {
                c.set(i, c.get(i) + c.get(i + 1));
            }
            size --;
        }
        int ret = c.get(0);
        return ret;
    }

    /**
     * 将数组num的全排列保存在全局变量list中
     * @param num 存储需要全排列的所有数
     * @param path 选择数字的路径
     * @param depth 树结构的第几层
     * @param used 标识num中数是否已经使用过
     */
    private static void wholeArrangement(int[] num, List<Integer> path, int depth, boolean[] used) {
        if (depth == n) {
            // 当递归到第num.length层则得到一个结果
            if (count(path, n) == sum) {
                for (int j = 0; j < n; j++) {
                    System.out.print(path.get(j));
                    if (j != n - 1) {
                        System.out.print(" ");
                    }
                }
                flag = true;
                System.exit(0);
            }
            return;
        }
        for (int i = 0; i < num.length; i++) {
            if (!used[i]) {
                // 这个数还未被使用过
                path.add(num[i]);
                used[i] = true;
                wholeArrangement(num, path, depth + 1, used);
                path.remove(path.size() - 1);
                used[i] = false;
            }
        }
    }
}
